package com.mdnote.practice.binary_tree;

import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/14 0014
 * @description
 */
public class LeetCode652 {

    public static void main(String[] args) {
        LeetCode652 leetCode652 = new LeetCode652();


//        TreeNode treeNode = toTree("1,2,3,4,null,2,4,null,null,null,null,4,null,null,null,");
        TreeNode treeNode = toTree("10,2,22,1,12,1,1");

        List<TreeNode> duplicateSubtrees = leetCode652.findDuplicateSubtrees(treeNode);

        duplicateSubtrees.forEach(t -> System.out.println(t.val));

    }

    private static TreeNode toTree(String arrStr) {

        String[] strs = arrStr.split(",");
        ArrayList<TreeNode> nodeList = new ArrayList<>();
        for (String str : strs) {
            if ("null".equals(str)) {
                nodeList.add(null);
            } else {
                nodeList.add(new TreeNode(Integer.parseInt(str)));
            }
        }

        return _buide(0, nodeList);
    }

    private static TreeNode _buide(Integer index, ArrayList<TreeNode> nodeList) {
        // Terminator
        if (index >= nodeList.size() || nodeList.get(index) == null) {
            return null;
        }
        TreeNode node = nodeList.get(index);
        node.left = _buide(index * 2 + 1, nodeList);
        node.right = _buide(index * 2 + 2, nodeList);

        return node;
    }

    private HashMap<String, Integer> map = new HashMap<>();
    private LinkedList<TreeNode> resList = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        _seriablize(root);

        return resList;
    }


    private String _seriablize(TreeNode node) {
        if (node == null) {
            return "#";
        }

        String left = _seriablize(node.left);
        String right = _seriablize(node.right);

        String cur = left + ","+ right + "," + node.val;

        // 这里就可以判断是否包含重复
        int freq = map.getOrDefault(cur, 0);
        if (freq == 1) {
            resList.add(node);
        }
        map.put(cur, freq + 1);
        return cur;
    }

      public static class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
}
